package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2023-08-05 14:55
 */
public class DG21合并两个有序链表 {


    public static void main(String[] args) {
        ListNode list1 = new ListNode(1,new ListNode(2,new ListNode(4,null)));
        ListNode list2 = new ListNode(1,new ListNode(3,new ListNode(4,null)));

        ListNode listNode = mergeTwoLists(list1, list2);

        System.out.println(listNode);
    }

    /**
     * 选头节点较小的链表 开始往后遍历 直到遇到next节点大于另外一个链表时 将此链表的next节点指向另一个链表 此节点链表的next节点作为新节点存在 如果节点为空 则结束遍历
     *
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode one ,two;
        if(list1.val <= list2.val){
            one = list1;
            two = list2;
        }else {
            one = list2;
            two = list1;
        }
        ListNode current = one;
        while (current != null || two != null){
            while (current.next.val<=two.val){
                current = current.next;
                if(current.next == null){
                    current.next = two;
                    return one;
                }
            }
            ListNode temp = current.next;
            current.next = two;
            current = two;
            two = temp;
        }

        return one;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
